package 题目集.单调栈or队列.单调栈;

import org.junit.Test;

/**
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 * https://leetcode.cn/problems/largest-rectangle-in-histogram/description/
 */
public class 柱状图中最大的矩形 {
    /**
     * 暴力解:
     *      枚举每一个柱子，以该柱子为最低高度，找到左右第一个比自己小的柱子（不包含），计算面积。
     *      时间复杂度：O(n^2)
     * 单调栈解：
     *      以每个柱子为中心，找到左右第一个比自己小的柱子设为l[i]和r[i]。
     *      该柱子的最大面积为：(r[i]-l[i]-1)*heights[i]
     *      时间复杂度：O(n)
     */
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        int[] stack = new int[n];
        int top = -1;
        for (int i = 0; i < n; i++) {
            while (top != -1 && heights[stack[top]] >= heights[i]) {    //如果这里是大于的话，就是右边界正常，左边界异常
                right[stack[top--]] = i;
            }
            left[i] = top == -1 ? -1 : stack[top];
            stack[++top] = i;
        }
        while (top != -1) {
            right[stack[top--]] = n;
        }
        //这个for可以省略
        //这里为什么可以不用修正存在重复值？因为发生重复值只会有一个重复值的右边界不正常。另一个重复值的右边界是正常的，而他们的面积又是一样的，所以可以不修复。
        for (int i = right.length - 1; i >= 0; i--) {
            //如果当前值和右边界值相等，那么右边界值就是右边界值的右边界值
            //因为是从右向左修复的，所以右侧的值一定是已经修复过的。
            if (right[i] != n && heights[i]==heights[right[i]]) {
                right[i] = right[right[i]];
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, (right[i] - left[i] - 1) * heights[i]); //-1是因为不包含左右边界
        }
        return res;
    }

    @Test
    public void test() {
        System.out.println(largestRectangleArea(new int[]{2, 1, 5, 6, 2, 3}));
    }
}
